package BasicClass.Four;

public class Test_Thirteenth {
    public static void main(String[] args) {

    }

    /**
     *现在有两个无环单链表，若两个链表的长度分别为m和n，请设计一个时间复杂度为O(n + m)，额外空间复杂度为O(1)的算法，判断这两个链表是否相交。
     *
     * 给定两个链表的头结点headA和headB，请返回一个bool值，代表这两个链表是否相交。保证两个链表长度小于等于500。
     *
     * 思路：两组链表，循环到最后一个节点，相等就相交
     * @param headA
     * @param headB
     * @return
     */
    public boolean chkIntersect(ListNode headA, ListNode headB) {
        if(headA == null || headB == null){
            return false;
        }
        ListNode curA = headA;
        while (curA.next != null){
            curA = curA.next;
        }
        ListNode curB = headB;
        while (curB.next != null){
            curB = curB.next;
        }
        return curA == curB;
    }

    public class ListNode {
        int val;
        ListNode next = null;

        ListNode(int val) {
            this.val = val;
        }
    }
}
